package agorithm.week2.classOne;

import java.util.*;

/**
 * 49. 字母异位词分组
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 *
 * 示例:
 *
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 *   ["ate","eat","tea"],
 *   ["nat","tan"],
 *   ["bat"]
 * ]
 * 说明：
 *
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 */
public class GroupAnagrams {
    public static void main(String[] args) {
        String[] commands = {"eat", "tea", "tan", "ate", "nat"};
        System.out.println(groupAnagrams(commands));
    }
    private boolean checkMapIsSame(Map<String,Integer> map1,Map<String,Integer> map2){
        if(map1.size() != map2.size()) return false;
        for(String key : map1.keySet()){
            if(!map2.containsKey(key) || map2.get(key) != map1.get(key))return false;
        }
        return true;
    }
    /**
     * 字母排序后存入 Map<String,List<String>>
     * 字母乱序组成后的字符串，排序后是一样的字符串
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        //  下标表示字母的hashkey,value表示字母出现的次数
        Map<String,List<String>> groupMap = new HashMap<>();
        for(int i = 0;i < strs.length; i++){
            String key = hashKey(strs[i]);
            List<String> list = groupMap.get(key);
            if(list == null){
                list = new ArrayList<>();
            }
            list.add(strs[i]);
            groupMap.put(key,list);
        }
        List<List<String>> ans = new ArrayList<>();
        for(List<String> list : groupMap.values()){
            ans.add(list);
        }
        return ans;
    }

    private static String hashKey(String s){
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return new String(arr);
    }
}
